package com.LeeCode;

/**
 * 有序三元组中的最大值 II
 */

public class Code2874 {
    public static void main(String[] args) {
        int[] nums = {1, 10, 3, 4, 19};
        System.out.println(new Code2874().maximumTripletValue(nums));
    }

    public long maximumTripletValue(int[] nums) {
        long ans = 0;
        int maxDiff = Integer.MIN_VALUE;  // nums[i] - nums[j] 的最大值
        int maxLeft = nums[0];          // nums[0..j-1] 中的最大值

        // 遍历j的位置
        for (int j = 1; j < nums.length - 1; j++) {
            // 更新左侧最大值
            maxLeft = Math.max(maxLeft, nums[j - 1]);

            // 更新最大差值 (nums[i] - nums[j])
            maxDiff = Math.max(maxDiff, maxLeft - nums[j]);

            // 计算以当前j为中间元素的最大三元组值
            ans = Math.max(ans, (long) maxDiff * nums[j + 1]);
        }

        return ans;
    }
}
